package org.infoset.xml.util;

import java.util.*;
import org.infoset.xml.*;

public abstract class TreeTraversal<Context> {
   protected boolean ok;
   protected Context context;

   public TreeTraversal() {
   }

   public void start(Context context) {
      this.context = context;
   }

   public Context end() {
      return context;
   }

   public Context traverse(Parent n) { 
      return traverse(n,null);
   }

   public Context traverse(Parent n,Context context) {
      ok = true;
      start(context);
      loop(n);
      return end();
   }

   public Context traverseChildren(Parent p) { 
      return traverseChildren(p,null);
   }

   public Context traverseChildren(Parent p,Context context) {
      ok = true;
      start(context);
      Iterator<Child> children = p.iterator();
      while (ok && children.hasNext()) {
         loop(children.next());
      }
      return end();
   }
   
   public abstract void visit(Child c,boolean start);

   protected void loop(Child n) {
      Child startingItem = n;
      Child current = n;
      visit(current,true);

      while (current!=null) {

         // Move the the left-most child
         if (current instanceof Parent) {
            Parent p = (Parent)current;
            if (!p.isEmpty()) {
               current = p.get(0);
               visit(current,true);
               continue;
            }
         }
         
         // we're now at a leaf, so move to its siblng
         
         Child next = current.getFollowingSibling();
         if (next!=null) {
            visit(current,false);
            current = next;
            visit(current,true);
            continue;
         }
         
         // we're done with this subtree
         visit(current,false);
         
         // No sibling, so move to nearest ancestor with following sibling
         
         current = current.getParent();
         
         Child nextCurrent = null;
         while (current!=startingItem && current!=null && nextCurrent==null) {
            // We're done with this item too
            visit(current,false);
            next = current.getFollowingSibling();
            if (next==null) {
               // We are at the right most child, so go to the parent
               current = current.getParent();
            } else {
               // We have a following sibling, so use that as current
               nextCurrent = next;
            }
         }
         // If we didn't start with a document item, we need to call the final 
         // visit for the starting item.
         if (current==startingItem) {
            visit(current,false);
         }
         current = nextCurrent;
         if (current!=null) {
            visit(current,true);
         }
         
      }
      
   }
}
